home *** CD-ROM | disk | FTP | other *** search
/ The World of Computer Software / The World of Computer Software.iso / lnklst10.zip / LINKLIST.DOC < prev    next >
Text File  |  1993-01-19  |  10KB  |  279 lines
  1.  
  2.          Linked List algorithms and implementation, version 1.0.
  3.  
  4.        All code and documentation is (c) Copyright 1993 SpeedSOFT
  5.             Development and Ben Morris.  All rights reserved.
  6.  
  7.  
  8. INTRODUCTION
  9. ---------------------------------------------------------------------------
  10.  
  11. This  code  implements  a  linked-list  algorithm using standard techniques
  12. (ie:  a  dual  circular  list).   Although  standard,  the code is fast and
  13. memory-efficient.
  14.  
  15. The  purpose behind  writing this code was  simple: nobody else would  give
  16. me any.  It's funny, actually,  because it took about 30 minutes  to write.
  17. Is it  my imagination, or are people becoming more selfish? <grin>.
  18.  
  19. Anyway, enough moral lecturing.
  20.  
  21.  
  22.  
  23. DESCRIPTION
  24. ---------------------------------------------------------------------------
  25.  
  26. (If you already  know what a  linked list is  (and what its  benefits are),
  27. then skip to the next section.)
  28.  
  29. A linked list is an alternative to a 'data array'.  Although slightly  more
  30. difficult to  use than  an array  (which is  built-in to  any language),  a
  31. linked list is faster and uses memory more efficiently.
  32.  
  33. For example:  Suppose  you needed to load  a lot of structured  information
  34. (ie: Each 'block' of information  is identical in size and  structure) into
  35. memory.  The obvious way to do so would be to declare an array of  'blocks'
  36. and  load  the  data  into  the  array  sequentially.  However, there is no
  37. conventional  (or  simple)  way  to  expand  an  array  should  it  be  too
  38. small to receive all  the data.  On  the other hand, there  would be wasted
  39. memory in the array if it was not completely used.  And, if members of  the
  40. array have to be moved or deleted, a lot of processor time may be  required
  41. to reassign the necessary pointers in the array.
  42.  
  43. A linked list solves the above  problems with elegance.  The first,  memory
  44. usage, is quite simple:  A linked list will  use only the amount  of memory
  45. required, and not  a byte more  (excluding pointer overhead).   Each 'node'
  46. in the list  (identical to an  index in an  array) contains three  members.
  47. The first  and second  are pointers  to the  previous and  subsequent nodes
  48. respectively, and the  third node is  a 'data' pointer.   It is this  third
  49. member that points to the data stored in the node.
  50.  
  51. Although  each  node  in  this  linked   list  method  requires  12  or   6
  52. additional bytes  (depending on  the memory  model used)  for pointers, the
  53. savings are quite considerable when using a large amount of data.
  54.  
  55. The other  memory advantage  is that  each node  in the  list can contain a
  56. different  size  data  block.   Of  course,  it  is up to the programmer to
  57. determine and retrieve the size of each block.
  58.  
  59. Linked lists can  be dynamically expanded  and contracted by  inserting and
  60. deleting nodes (see next section for details).  Deleting nodes in a  linked
  61. list is considerably faster than doing  so with arrays:  A maximum  of four
  62. pointers are  re-arranged in  a list.   The same  goes for  inserting nodes
  63. anywhere in the list.
  64.  
  65. I did mention that linked lists are more awkward than arrays to  implement.
  66. While  indeces  in  an  array  can  be  referenced  simply by using pointer
  67. mathematics (ie: files[14]),  the data in  a linked list  must be retrieved
  68. with a call to a function.
  69.  
  70. CAUTIONS.  A  linked list is  only speed-effective if  no (or very  little)
  71. random access is performed.
  72.  
  73.  
  74.  
  75. USAGE
  76. ---------------------------------------------------------------------------
  77.  
  78. NB:     The 'C'  structure NODE (and NODEPTR) is used with  all linked-list
  79.         functions in this source.
  80.  
  81. The header file LINKLIST.H must be #included to use the code.
  82.  
  83. Each linked list  must have a  'head' node. This  node, which is  passed to
  84. some functions,  is used  by LINKLIST.C.  NOTE that  once defined, the head
  85. node MUST NOT BE CHANGED IN ANY WAY outside of LINKLIST.C.
  86.  
  87. To define  the head  node, assign  it the  return value  from the  function
  88. InitList().  For example,
  89.  
  90.         NODEPTR head = InitList();
  91.  
  92. Calls to the  functions NodeInsert() and  NodeDelete() allow you  to insert
  93. and delete nodes in the list. For a detailed function reference, see below.
  94.  
  95. Data is  stored in  the 'data'  member of  a NODEPTR  structure.   The data
  96. member can  be allocated  with a  call to  NodeInsert(), or  with a call to
  97. malloc() (or  compat.) outside  of LINKLIST.C.   Note that  the head node's
  98. data member is always NULL.
  99.  
  100. Once  you're  finished  with  the  list,  call  DestroyList()  to  free all
  101. allocated memory.
  102.  
  103.  
  104.  
  105. FUNCTIONS
  106. ---------------------------------------------------------------------------
  107.  
  108. NOTE: Since LINKLIST.C  doesn't depend on  any internal variables,  you can
  109. use  as  many  linked  lists  as  the  system  has  memory  for.   The  one
  110. restriction is that you  must define a different  head node for every  list
  111. you use.
  112.  
  113. The only  external functions  used in  LINKLIST.C are  malloc() and free().
  114. The   calls   to   these   functions   can   be   replaced   by  compatible
  115. substitutes.
  116.  
  117. ALL functions here will work even if the head node is the only one  defined
  118. in a list.
  119.  
  120.  
  121. .................................................................InitList()
  122.  
  123. Function: Initializes a linked list.
  124.  
  125. Call    : NODEPTR InitList( void );
  126.  
  127. Returns : Pointer to the head node, or NULL: Not enough memory.
  128.  
  129. Remarks : Call this  function  to  initialize the  'head node'  for a list.
  130.           Subsequent calls to functions that  require a 'head node' as  one
  131.           of  the  parameters  should  be  passed the pointer returned from
  132.           this function.
  133.  
  134.  
  135.  
  136. ...............................................................NodeInsert()
  137.  
  138. Function: Inserts a node in the linked list.
  139.  
  140. Call    : NODEPTR NodeInsert( NODEPTR previous, size_t len );
  141.  
  142.           previous:  A pointer to the  previous node in the list.   The new
  143.                      node will be inserted after this node (and before  any
  144.                      subsequent nodes).   You can use  the head node  here,
  145.                      if desired.
  146.  
  147.           len     :  The number of bytes to allocate for the 'data'  member
  148.                      of  the  NODEPTR  structure.   Specify  0  here if you
  149.                      don't want to allocate memory immediately.
  150.  
  151. Returns : A  pointer  to  the  allocated  and  inserted  node, or NULL: Not
  152.           enough memory.
  153.  
  154. Remarks : NodeInsert() inserts a node in the list after the node  specified
  155.           in 'previous'.   Unless the parameter  'len' is set  to 0, memory
  156.           will be allocated in the 'data' member of the NODEPTR.
  157.  
  158.           Note that the data member is never used inside of LINKLIST.C.
  159.  
  160.  
  161.  
  162. ...............................................................NodeDelete()
  163.  
  164. Function: Deletes a node from the linked list.
  165.  
  166. Call    : void NodeDelete( NODEPTR ndp );
  167.  
  168.           ndp     :  A pointer to the node to delete from the list.
  169.  
  170. Returns : Nothing.
  171.  
  172. Remarks : NodeDelete()  will  delete 'ndp'  from the  linked list, free its
  173.           'data' member (if  allocated), and free  the memory allocated  in
  174.           'ndp'.  Note that NO error checking is performed to see that  the
  175.           pointer passed is valid.
  176.  
  177.  
  178.  
  179. .............................................................NodeNumtoPtr()
  180.  
  181. Function: Converts a node number to its pointer in the list.
  182.  
  183. Call    : NODEPTR NodeNumtoPtr( int num, NODEPTR head_ndp );
  184.  
  185.           num     :  The  number  of  the  node  to  return a  pointer  for
  186.                      (starting at 0).
  187.  
  188.           head_ndp:  The head node in the list.
  189.  
  190. Returns : A pointer to the retrieved  node, or NULL: There is no node  with
  191.           that number.
  192.  
  193. Remarks : NodeNumtoPtr() will return a NODEPTR corresponding to its  number
  194.           (sequence) in  the list.   If NULL  is returned,  then the number
  195.           passed was  too large  (ie: the  list doesn't  contain that  many
  196.           entries).
  197.  
  198.  
  199.  
  200. .............................................................NodePtrtoNum()
  201.  
  202. Function: Converts a node pointer to its number (sequence) in the list.
  203.  
  204. Call    : int NodePtrtoNum( NODEPTR sndp, NODEPTR head_ndp );
  205.  
  206.           sndp    :  The pointer to convert to a number.
  207.  
  208.           head_ndp:  The head node in the list.
  209.  
  210. Returns : The number  (sequence) of 'sndp' in  the list, or -1:  'sndp' was
  211.           not found.
  212.  
  213. Remarks : NodePtrtoNum() will return a number corresponding to its  NODEPTR
  214.           in  the  list  (starting  at  0).   If  -1  is returned, then the
  215.           NODEPTR passed was not found in the list.
  216.  
  217.  
  218.  
  219. .................................................................NodePrev()
  220.  
  221. Function: Returns a node's previous node in the list.
  222.  
  223. Call    : NODEPTR NodePrev( NODEPTR ndp );
  224.  
  225.           ndp     :  The node whose previous node is to be returned.
  226.  
  227.  
  228.  
  229. .................................................................NodeNext()
  230.  
  231. Function: Returns a node's next node in the list.
  232.  
  233. Call    : NODEPTR NodeNext( NODEPTR ndp );
  234.  
  235.           ndp     :  The node whose next node is to be returned.
  236.  
  237.  
  238.  
  239. ................................................................NodeFirst()
  240.  
  241. Function: Returns a pointer to the first (non-head) node in the list.
  242.  
  243. Call    : NODEPTR NodeFirst( NODEPTR head_ndp );
  244.  
  245.           head_ndp:  The head node of the list.
  246.  
  247.  
  248.  
  249. .................................................................NodeLast()
  250.  
  251. Function: Returns a pointer to the last node in the list.
  252.  
  253. Call    : NODEPTR NodeLast( NODEPTR head_ndp );
  254.  
  255.           head_ndp:  The head node of the list.
  256.  
  257.  
  258.  
  259. ................................................................NodeTotal()
  260.  
  261. Function: Returns the total number of  nodes in a list (excluding the  head
  262.           node).
  263.  
  264. Call    : int NodeTotal( NODEPTR head_ndp );
  265.  
  266.           head_ndp:  The head node of the list.
  267.  
  268.  
  269.  
  270. ..............................................................DestroyList()
  271.  
  272. Function: Frees all memory for a list (destroys it).
  273.  
  274. Call    : void DestroyList( NODEPTR head_ndp );
  275.  
  276.           head_ndp:  The head node of the list.
  277.  
  278. NOTE    : The head node is destroyed in this call!
  279.